// https://leetcode.cn/problems/search-insert-position/
/*
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

例如：
nums = [1,3,5,6], target = 5 输出2

*/

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
		int len = nums.size();
		int left = 0;
		int right = len - 1;
		int mid = 0;
		while(left < right){
			mid = (left + right) / 2;
			if(nums[mid] > target){
				right = mid;
			}else if(nums[mid] < target){
				left = mid + 1;
			}else{
				left = mid;
				while(left > 0 && nums[left] == nums[left - 1]){
					left--;
				}
				break;
			}
		}
		// 注意点处理最大值右边界问题
		if(nums[left] < target){
			left++;
		}
		return left;
    }
};

int main(){
	Solution so;
	vector<int> nums = {1, 3, 5, 6};
	int target = 7;
	// int target = -1;
	int index = so.searchInsert(nums, target);
	cout << index << endl;
	return 0;
}